#
# @lc app=leetcode.cn id=438 lang=python3
#
# [438] 找到字符串中所有字母异位词
#

# @lc code=start
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        p_count = [0] * 26
        s_count = [0] * 26

        if len(s) < len(p):
            return res
        
        lenp = len(p)
        for i in range(lenp):
            p_count[ord(p[i])-ord('a')] += 1


        



        for j in range(lenp):
            s_count[ord(s[j])-ord('a')] += 1

        sta = True
        for k in range(26):
            if p_count[k] != s_count[k]:
                sta = False
                break
        if sta:
            res.append(0)

        for i in range(1, len(s)-lenp+1):
            s_count[ord(s[i-1])-ord('a')] -= 1
            s_count[ord(s[i+lenp-1])-ord('a')] += 1

            sta = True
            for k in range(26):
                if p_count[k] != s_count[k]:
                    sta = False
                    break
            if sta:
                res.append(i)
        return res
# @lc code=end

